package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/09/21 10:21
 **/
public class Day19_1_Num854_KSimilarity {
    class Solution {
        int min = Integer.MAX_VALUE;
        public int kSimilarity(String s1, String s2) {
            dfs(s1.toCharArray(), s2.toCharArray(), 0, s1.length(), 0);
            return min;
        }
        private void dfs(char[] arr1, char[] arr2, int cur, int len, int count){
            if(cur == len){  // 当遍历完字符串，更新min 交换次数
                min = Math.min(min, count);
                return;
            }
            if(count >= min) return; // 剪枝
            if(arr1[cur] != arr2[cur]){
                for(int i = cur + 1; i < len; ++i){
                    if(arr1[cur] == arr2[i]){
                        swap(arr2, cur, i);
                        dfs(arr1, arr2, cur + 1, len, count + 1);
                        swap(arr2, cur, i);
                    }
                }
            }else {
                dfs(arr1, arr2, cur + 1, len, count);
            }
        }
        // 交换三连
        private void swap(char[] arr, int i, int j){
            char tem = arr[i];
            arr[i] = arr[j];
            arr[j] = tem;
        }
    }
}